package com.wwz.leetcode;

import java.util.HashMap;
import java.util.Map;



/**
 * <p>Description:二叉树题目</p>
 * <p>Copyright: Copyright (c)2020</p>
 * <p>Company: Tope</p>
 * <P>Created Date :2020-06-04</P>
 * <P>@version 1.0</P>
 */
public class BinaryTree {

    //前序遍历:首先访问根结点然后遍历左子树，最后遍历右子树。                    ->根左右
    //中序遍历:首先遍历左子树，然后访问根结点，最后遍历右子树。                  ->左根右
    //后序遍历:先左后右再根，即首先遍历左子树，然后遍历右子树，最后访问根结点。  ->左右根

    public static void main(String[] args) {
        int[] preorder = {3,9,20,15,7};
        int[] inorder = {9,3,15,20,7};
        buildTree(preorder,inorder);
    }

    public static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }

    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        Map<Integer, Integer> indexMap = new HashMap<Integer, Integer>();
        int length = preorder.length;
        for (int i = 0; i < length; i++) {
            indexMap.put(inorder[i], i);
        }
        TreeNode root = buildTree(preorder, 0, length - 1, inorder, 0, length - 1, indexMap);
        //[3,9,20,null,null,15,7]
        return root;
    }

    public static TreeNode buildTree(int[] preorder, int preorderStart, int preorderEnd, int[] inorder, int inorderStart, int inorderEnd, Map<Integer, Integer> indexMap) {
        if (preorderStart > preorderEnd) {
            return null;
        }
        int rootVal = preorder[preorderStart];
        TreeNode root = new TreeNode(rootVal);
        if (preorderStart == preorderEnd) {
            return root;
        } else {
            int rootIndex = indexMap.get(rootVal);
            int leftNodes = rootIndex - inorderStart, rightNodes = inorderEnd - rootIndex; //左右子树各有多少节点
            TreeNode leftSubtree = buildTree(preorder, preorderStart + 1, preorderStart + leftNodes, inorder, inorderStart, rootIndex - 1, indexMap);
            TreeNode rightSubtree = buildTree(preorder, preorderEnd - rightNodes + 1, preorderEnd, inorder, rootIndex + 1, inorderEnd, indexMap);
            root.left = leftSubtree;
            root.right = rightSubtree;
            return root;
        }
    }

}
